/*
题目：二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。
https://leetcode.cn/problems/binary-tree-maximum-path-sum/
 */
public class MaxPathSum {
    int ans = Integer.MIN_VALUE;//记录答案
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return ans;
    }

    //得出最大贡献值
    private int maxGain(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftGain = Math.max(maxGain(root.left), 0); //分别记录左右子树的贡献值
        int rightGain = Math.max(maxGain(root.right), 0); //并且只有贡献值大于0的时候才取

        int curGain = leftGain + rightGain + root.val;
        if (curGain > ans) {
            ans = curGain;
        }
        return root.val + Math.max(leftGain, rightGain); //该节点的最大贡献值
    }
}
